from typing import List


class Solution:
    def expand(self, s: str) -> List[str]:
        l, r = s.find("{"), s.find("}")

        if l == -1:
            return [s]

        left = s[:l]
        now_options = sorted(s[l + 1:r].split(","))
        right_options = self.expand(s[r + 1:])

        ans = []
        for now_option in now_options:
            for right_option in right_options:
                ans.append(left + now_option + right_option)
        return ans


if __name__ == "__main__":
    print(Solution().expand("{a,b}c{d,e}f"))  # ["acdf","acef","bcdf","bcef"]
    print(Solution().expand("abcd"))  # ["abcd"]
